from math import pow
from types import TupleType


class ClusteringError(Exception):
    pass


class KMeansCluster:
    def __init__(self, data=None, dataType=None, enabled=None):
        self.__data = data
        self.__data_type = dataType
        self.__enabled = enabled
        self.__initial_length = len(data)

        # test if each item is of same dimensions
        if len(data) > 1 and isinstance(data[0], TupleType):
            control_length = len(data[0])
            for item in data[1:]:
                if len(item) != control_length:
                    raise ValueError("Each item in the data list must have \
                                      the same amount of dimensions. Item",
                                      item, "was out of line!")
        # now check if we need and have a distance function
        if len(data) > 1 and not isinstance(data[0], TupleType):
            raise ValueError("You supplied non-standard items but no \
                              distance function! We cannot continue!")

    def getclusters(self, n):
        # only proceed if we got sensible input
        if n <= 1:
            raise ClusteringError("When clustering, you need to ask for at \
                                   least two clusters! You asked for %d" % n)

        # return the data straight away if there is nothing to cluster
        if self.__data == [] or \
           len(self.__data) == 1 or \
           n == self.__initial_length:
            return self.__data

        # It makes no sense to ask for more clusters than data-items available
        if n > self.__initial_length:
            raise ClusteringError("Unable to generate more clusters than \
                                   items available. You supplied %d items, \
                                   and asked for %d clusters." %
                                   (self.__initial_length, n))

        self.initialiseClusters(self.__data, n)

        items_moved = True  # tells us if any item moved between the clusters,
                            # as we initialised the clusters, we assume that
                            # is the case
        while items_moved is True:
            items_moved = False
            for cluster in self.__clusters:
                for item in cluster:
                    res = self.assign_item(item, cluster)
                    if items_moved is False:
                        items_moved = res
        return self.__clusters

    def assign_item(self, item, origin):
        closest_cluster = origin
        for cluster in self.__clusters:
            if self.minkowski_distance(item, self.centroid(cluster)) \
               < self.minkowski_distance(item,
                                         self.centroid(closest_cluster)):
                closest_cluster = cluster

        if closest_cluster != origin and len(origin) > 1:
            self.move_item(item, origin, closest_cluster)
            return True
        else:
            return False

    def move_item(self, item, origin, destination):
        destination.append(origin.pop(origin.index(item)))

    def initialiseClusters(self, input, clustercount):
        # initialise the clusters with empty lists
        self.__clusters = []
        for x in xrange(clustercount):
            self.__clusters.append([])

        # distribute the items into the clusters
        count = 0
        for item in input:
            self.__clusters[count % clustercount].append(item)
            count += 1

    def centroid(self, list):
        "returns the central vector of a list of vectors"
        out = []
        for i in range(len(list[0])):
            if self.__data_type[i] != "Text" and \
               ((self.__enabled is None) or self.__enabled[i]):
                out.append(self.median([x[i] for x in list]))
            else:
                out.append(list[0][i])
        return tuple(out)

    def minkowski_distance(self, x, y):
        assert(len(y) == len(x))
        assert(x >= 1)
        sum = 0
        for i in range(len(x)):
            if (self.__enabled is None) or self.__enabled[i]:
                if self.__data_type[i] == "Int" or \
                   self.__data_type[i] == "Float":
                    sum += (abs(x[i]-y[i]) * abs(x[i]-y[i]))
                elif self.__data_type[i] == "Binary":
                    sum += (abs(x[i]-y[i]) * 0xFFFF)
        return pow(sum, 0.5)

    def median(self, numbers):
        # Sort the list and take the middle element.
        n = len(numbers)
        copy = numbers[:] # So that "numbers" keeps its original order
        copy.sort()
        if n & 1:         # There is an odd number of elements
            return copy[n/2]
        else:
            return (copy[n/2 - 1] + copy[n/2]) / 2.0


